class Solution {
public:
    int integerReplacement(int x) {
        int ans = 0;
        long long n = x;
        while(n != 1){
            if(n == 3){
                return ans+2;
            }
            if((n & 1) == 0){
                n >>= 1;
            }else{
                if(((n >> 1) & 1) == 0){
                    n -= 1;
                }else{
                    n += 1;
                }
            }
            ans++;
        }
        return ans;
    }
};
